package com.sicheng.lc.lc笔试.网易篇;

import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/20 23:10
 */
public class 三元组 {
    /**
     * 一个数组，n <= 100000，arr[i] <= 10^9
     * 需要找到这样的三元组(i,j,k)，i < j < k，且 ai == ak && ai > aj。问有多少个
     */
    static int N = (int) 1e5;
    static int[] tree = new int[N + 1];
    static int query(int x) {
        int res = 0;
        for (int i = x; i > 0; i -= i & -i) {
            res += tree[i];
        }
        return res;
    }

    static void add(int x) {
        for (int i = x; i <= N; i += i & -i) {
            tree[i]++;
        }
    }

    static void clear() {
        for (int i = 0; i <= N; i++) {
            tree[i] = 0;
        }
    }

    /**
     * 离散化 + 树状数组
     * O(N^2)
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];

        for (int i = 0; i < a.length; i++) {
            a[i] = sc.nextInt();
            b[i] = a[i];
        }
        b = IntStream
                .of(b)
                .distinct()
                .sorted()
                .toArray();
        long res = 0;
        for (int i = 0; i < a.length - 2; i++) {
            for (int k = i + 1; k < a.length; k++) {
                if (a[i] == a[k] && k > i + 1) {
                    int t = leftSearch(b, a[k]);
                    res += query(t - 1);
                }
                add(a[k]);
            }
            clear();
        }

        System.out.println(res);
    }

    static int leftSearch(int[] nums, int x) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[mid] >= x) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l + 1;
    }
}
